//https://leetcode.cn/problems/longest-common-subsequence/description/


class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int lon1 = text1.size(), lon2 = text2.size(), ans = 0;
        vector<vector<int>> dp(lon1 + 1, vector<int> (lon2 + 1));
        text1 = " " + text1;
        text2 = " " + text2;
        //dp[0][0] = text1[0] == text2[0] ? 1 : 0;
        for(int i = 1; i <= lon1; i++)
        {
            for(int j = 1; j <= lon2; j++)
            {
                if(text1[i] == text2[j])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};